// 给定一个代表三角形的二维数组triangle，triangle共有n行，其中第i行（从0开始编号），包含了i+1个数
// 我们每一步只能从当前位置移动到下一行中相邻的节点上，也就是说，如果正位于第i行第j列的节点，那么下一步可以移动到第i+1行第j列的位置上，或者第i+1行，第j+1列的位置上
// 要求：找出自顶向下的最小路径和

// 解题思路：动态规划
// 1. 划分阶段：按照行数进行阶段划分
// 2. 定义状态：定义状态dp[i][j]表示为：从顶部走到第i行，第j列的最小路径和
// 3. 状态转移方程：
//  每一步只能从当前位置移动到下一行中相邻的节点上，想要移动到第i行，第j列的位置，上一步只能在第i-1行，第j-1列，或者第i-1行，第j列上
// 其状态转移方程为dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
// 4. 初始条件
// 在第0行，第j列时，最小路径和为triangle[0][0]，即dp[0][0] = triangle[0][0]
// 5. 最终结果
// 遍历一遍dp[size-1]行的每一列，求出最小值即为最终结果
// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)

function minimumTotal(triangle) {
    let dp = new Array(triangle.length).fill(0).map(_ => new Array(triangle.length).fill(0))
    dp[0][0] = triangle[0][0]
    for (let i = 1; i < triangle.length; i++) {
        // 第一列，只有一种方式
        dp[i][0] = dp[i-1][0] + triangle[i][0]
        for (let j = 1; j < i; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
        }       
        // 最后一列，只有一种方式 
        dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]
    }
    return Math.min(...dp[triangle.length - 1])
}

let triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
console.log(minimumTotal(triangle))